package exer2;

class Solution {
    public static void main(String[] args) {
        int []preOrder= {-1};
        int []inOrder= {-1};
        Solution solution = new Solution();
        solution.buildTree(preOrder,inOrder);
    }
    private  int preIndex=0;//定义前序遍历的下标
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildChild(preorder,inorder,0,inorder.length-1);
    }
    //定义find方法，来找下标
    public int find(int[]inorder,int value){
        for(int i=0;i<inorder.length;++i){
            if(inorder[i]==value){ 
                return i;
            }
        }
        return -1;
    }
    //定义创建孩子结点的方法
    
    public TreeNode buildChild(int[] preorder, int[] inorder,int begin,int end){
        if(begin>end||preIndex>preorder.length-1){
            return null;
        }
          // 1.首先获取前序序列中节点的值
        int rootValue = preorder[preIndex];
        //更迭begin和right
        int rootIndex=find(inorder,rootValue);
 //检查root的有效性
        if(rootIndex==-1){
            return null;
        }
        //创建根结点
        TreeNode root=new TreeNode(rootValue);
        preIndex++;//前序数组向后遍历
        root.left=buildChild(preorder,inorder,begin,rootIndex-1);
        root.right=buildChild(preorder,inorder,rootIndex+1,end); 
        return root;
    }

}